//
function heapSort(arr) {
    const copy = [...arr]; // 创建副本，不修改原数组
    let len = copy.length;

    // 构建初始大顶堆（从最后一个非叶子节点开始调整）
    for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        heapify(copy, i, len);
    }

    // 逐步提取堆顶最大值到数组末尾
    for (let i = len - 1; i > 0; i--) {
        [copy[0], copy[i]] = [copy[i], copy[0]]; // 交换堆顶与末尾元素
        len--;
        heapify(copy, 0, len); // 调整剩余元素为堆
    }

    return copy;
}

// 调整以 i 为根的子树为大顶堆
function heapify(arr, i, heapSize) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    // 找到当前节点、左子节点、右子节点中的最大值
    if (left < heapSize && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < heapSize && arr[right] > arr[largest]) {
        largest = right;
    }

    // 若最大值不是当前节点，交换并递归调整
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, largest, heapSize);
    }
}

// 测试示例
const originalArr = [3, 1, 4, 1, 5, 9, 2, 6];
const sortedArr = heapSort(originalArr);

console.log(originalArr); // [3, 1, 4, 1, 5, 9, 2, 6]（原数组未修改）
console.log(sortedArr);    // [1, 1, 2, 3, 4, 5, 6, 9]